package leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class EvaluateReversePolishNotation {

	public static void main(String[] args) {
		String string = "123456+123";
		String[] tokens = {"2", "1", "+", "3", "*"};
		EvaluateReversePolishNotation object = new EvaluateReversePolishNotation();
//		System.out.println(object.getValue(string));
		System.out.println(object.evalRPN(tokens));
	}
	
	public int evalRPN(String[] tokens) {
		Stack<Integer> stack = new Stack<Integer>();
		int res = 0;
		String getIndexString = "+-*/";
		int a = 0, b = 0;
		for (String s : tokens) {
			if (s.equals("+") || s.equals("-") || s.equals("*")
					|| s.equals("/")) {
				int index = getIndexString.indexOf(s);
				switch (index) {
				case -1:
					break;
				case 0:
					res = stack.pop() + stack.pop();
					System.out.println("res+: " + res);
					stack.push(res);
					break;
				case 1:
					a = stack.pop();
					b = stack.pop();
					res = b - a;
					System.out.println("res-: " + res);
					stack.push(res);
					break;
				case 2:
					res = stack.pop() * stack.pop();
					System.out.println("res*: " + res);
					stack.push(res);
					break;
				case 3:
					a = stack.pop();
					b = stack.pop();
					res = b / a;
					System.out.println("res/: " + res);
					stack.push(res);
					break;
				default:
					break;
				}
			} else {
				// 由于可能是表达式
				// 所以还要进行求值
				stack.add(getValue(s));
			}
		}
		return stack.isEmpty() ? 0 : stack.pop();
	}
	
	public int getValue(String string){
		String[] operators = {"+", "-", "*", "/"};
		int index = 0;
		int operator = -1;
		for (int i = 0; i < operators.length; i++) {
			index = string.indexOf(operators[i]);
			if(index != -1){
				operator = i;
				break;
			}
		}
		if(index <= 0){
			int b = Integer.valueOf(string.substring(0, string.length()));
			return b;
		}
		int a = Integer.valueOf(string.substring(0, index));
		int b = Integer.valueOf(string.substring(index, string.length()));
		switch (operator) {
		case -1:
			return b;
		case 0:
			return a + b;
		case 1:
			return a - b;
		case 2:
			return a * b;
		case 3:
			return a / b;
		default:
			break;
		}
		return 0;
	}
}
